An image, especially a multi-valued image contains a very large amount of information, and when the image is stored or transmitted, its data amount causes a problem. Therefore, to store or transmit the image, a high efficient coding is employed for coding the image data, in which the multi-valued image has the redundancy removed, or the content of the multi-valued image is changed to the extent that the image quality degradation is visually unrecognizable to reduce the data amount. For example, in a JPEG recommended by the ISO and ITU-T as the international standard coding system for still image, the image data is subjected to a Discrete Cosine Transformation (DCT) into DCT coefficients for each block (8 pixels×8 pixels), each DCT coefficient being quantized, and further the quantized value is entropy coded to compress the image data. The compression techniques using this DCT include H261, MPEG1/2/4, in addition to the JPEG.
An Hadamard transformation is a process associated with this DCT transformation or a process for transforming the image data. The Hadamard transformation is an orthogonal transformation with a transformation matrix composed of the elements of “1” and “−1”, which is the simplest one that is represented only by addition and subtraction.
For this Hadamard transformation, a transformation matrix H2 for two-point Hadamard transformation is defined in the following way.
[Expression 1]
                              H          2                =                              1                          2                                ⁡                      [                                                            1                                                  1                                                                              1                                                                      -                    1                                                                        ]                                              (        1        )            
A typical N (=2N)-point Hadamard transformation matrix HN is recursively defined as a Kronecker product between the (N/2)-point Hadamard transformation matrix HN/2 and the two-point Hadamard transformation matrix H2.
[Expression 2]
                              H          N                =                                            H                              N                /                2                                      ⊗                          H              2                                =                                    1                              2                                      ⁡                          [                                                                                          H                                              N                        /                        2                                                                                                                        H                                              N                        /                        2                                                                                                                                                        H                                              N                        /                        2                                                                                                                        -                                              H                                                  N                          /                          2                                                                                                                                ]                                                          (        2        )            
A four-point Hadamard transformation matrix is obtained from the above definition in the following way.
[Expression 3]
                              H          4                =                              1            2                    ⁡                      [                                                            1                                                  1                                                  1                                                  1                                                                              1                                                                      -                    1                                                                    1                                                                      -                    1                                                                                                1                                                  1                                                                      -                    1                                                                                        -                    1                                                                                                1                                                                      -                    1                                                                                        -                    1                                                                    1                                                      ]                                              (        3        )            This four-point Hadamard transformation matrix is called a natural type, in which the base vectors are not arranged in sequency. Thus, if the permutation of the base vectors is repeated to shift the base vector in the second row to the fourth row, a transformation matrix WH4 having the base vectors arranged in sequency results.[Expression 4]
                              WH          4                =                              1            2                    ⁡                      [                                                            1                                                  1                                                  1                                                  1                                                                              1                                                  1                                                                      -                    1                                                                                        -                    1                                                                                                1                                                                      -                    1                                                                                        -                    1                                                                    1                                                                              1                                                                      -                    1                                                                    1                                                                      -                    1                                                                        ]                                              (        4        )            
This transformation matrix WH4 is called a Walsh type or a Walsh-Hadamard transformation matrix. It is well known that the Hadamard transformation is a reversible orthogonal transformation, in which both the natural type and the Walsh type are capable of the reversible transformation, and the transformation matrix is symmetrical.
It is generally said that the Hadamard transformation is a reversible transformation as is described above, which means that it is mathematically reversible. That is, it is supposed that no arithmetical operation error arises in the transformation and the reverse transformation. For this reversible transformation, it is required to perform the arithmetical operation in the fixed point and the floating point, and hold all the data of significant digits after the transformation processing.
However, in the Hadamard transformation in which the compression coding is supposed, there is a desire to reduce the number of significant digits as much as possible after the transformation processing. More specifically, the data after the decimal fractions that arises when the integer input data is transformed is grasped to have clearly more digits (information) than the input data, whereby it is indispensable to omit the data after the decimal fractions to compress the data. However, if this data after the decimal fractions is simply rounded, the reversible property is impaired. For example, four pieces of data, including 123, 78, 84 and 56, are subjected to the Hadamard transformation with a transformation matrix of the expression (4) in the following way.                170.5(=(123+78+84+56)/2), 30.5(=(123+78−84−56)/2), 8.5(=(123−78−84+56)/29, 36.5(=(123−78+84−56)/2)        
Rounding off the above values into the integer,                171, 31, 9, 37are obtained. Then, making the reverse transformation (with a transposed matrix of the transformation matrix, which is the same as the transformation matrix),        124, 78, 84, 56are obtained. In this way, the initial data “123” is altered into “124” through the Hadamard transformation and its reverse transformation. Thus, the Hadamard transformation to output the integer data does not guarantee the reversibility. In the following, the Hadamard transformation to output the integer data is called an integer type Hadamard transformation, and the integer type Hadamard transformation capable of making the reversible transformation is called an integer type reversible Hadamard transformation or a lossless Hadamard transformation.        
Conventionally, the lossless four-point Hadamard transformation was realized in the following way.                (a) Decompose the four-point Hadamard transformation matrix H4 into a product of triangular matrices with the diagonal elements “1”,        (b) Apply a row replacing operation Q on the original transformation matrix, and        (c) Decompose QH4 into a product of following matrices from the above (a) and (b).[Expression 5]        
                              QH          4                =                                            [                                                                    1                                                        0                                                        0                                                        0                                                                                        0                                                        1                                                        0                                                        0                                                                                        0                                                                              -                      1                                                                            1                                                        0                                                                                                              -                      1                                                                            0                                                        0                                                        1                                                              ]                        ⁡                          [                                                                    1                                                        0                                                                              1                      /                      2                                                                                                  1                      /                      2                                                                                                            0                                                        1                                                                              1                      /                      2                                                                                                                          -                        1                                            /                      2                                                                                                            0                                                        0                                                        1                                                        0                                                                                        0                                                        0                                                        0                                                        1                                                              ]                                ⁡                      [                                                                                -                    1                                                                    0                                                  0                                                  0                                                                              0                                                                      -                    1                                                                    0                                                  0                                                                              1                                                  0                                                  1                                                  0                                                                              0                                                                      -                    1                                                                    0                                                  1                                                      ]                                              (        5        )                            (d) Represent this transformation in a signal flow (as represented in FIG. 1),        (e) Round the data after the decimal fractions that arises in multiplication operation in this signal flow to make the integer data.        
The lossless four-point Hadamard transformation is implemented with the above items (a) to (e). Some supplementary explanation is given in the following.
The signal flow of FIG. 1 has a Ladder Network configuration which is often employed to implement a reversible transformation process. In this Ladder Network, the transformation process for outputting the integer data is made reversible by introducing a rounding process (200, 201 in FIG. 2) rounding the data to the output side of a multiplier 100, 101 in which the data after the decimal fractions is produced as a general method (in the field of reversible transformation process).
Herein, if the corresponding rounding process of the multiplication output is the same between the transformation process and the reverse transformation process, the content of the rounding process 200, 201 is arbitrary.
FIG. 2 shows a signal flow (capable of the reversible transformation) which is made reversible by introducing the rounding process into the signal flow of FIG. 1. This was a conventional arithmetical operation method for implementing the integer type reversible four-point Hadamard transformation.
A lossless 16-point Hadamard transformation is constructed by linking such lossless integer type reversible four-point Hadamard transformations at multistage. However, there is a dispersion in the average value of the error of each transformed output (a difference between mathematical transformation and lossless transformation) or the mean square error, giving rise to accurate transform coefficients and inaccurate transform coefficients.
Also, the conventional lossless two-dimensional DCT (Discrete Cosine Transformation) had a significant error of transformation with reference to the conventional two-dimensional DCT.